// https://leetcode.cn/problems/house-robber-ii/

// 题干：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
//      这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
//      同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
//      给定一个代表每个房屋存放金额的非负整数数组，
//      计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

// 示例：输入：nums = [2,3,2]
//      输出：3

// 碎语：打家劫舍的加强版，最后一位特殊处理
//       可以分类讨论，把题目化为打家劫舍1
//       化解环形
// 如果第一个偷了，那么可以在2 ~ n - 2随便偷
// 如果第一个没偷，那么可以在1 ~ n - 1随便偷，即打家劫舍1

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        vector<int> f(n), g(n);

        // 假如第一个没偷
        f[0] = g[0]= 0;

        for (int i = 1 ; i < n ; i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        int max1 = max(f[n - 1], g[n - 1]);

        // 假如第一个偷了
        f[0] = g[0] = nums[0];
        f[1] = g[1] = nums[0];

        for (int i = 2 ; i < n - 1 ; i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        f[n - 1] = f[n - 2], g[n - 1] = g[n - 2];
        int max2 = max(f[n - 1], g[n - 1]);

        return max(max1, max2);
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {2,3,2};

    cout << sol.rob(nums) << endl;

    return 0;
}